|
|
CS 116 Tutorial 2 (Solutions): Making Decisions in Python
Reminders:
- Assignment 02 is due on Wednesday, Jan. 29th at 10am
- Ensure you understand the results of calling
choices(8), choices(10), choices(100), choices(111), choices(250):
def choices(n):
answer = 0
if n % 2 == 0:
answer = answer + 1
if n % 3 == 0:
answer = answer + 1
elif n % 5 == 0:
answer = answer + 1
else:
answer = 10 * answer
if n % 10 == 0:
answer = answer - 1
if n % 4 == 0:
answer = answer // 2
else:
answer = 2 * answer
return answer
choices(8) => 10
choices(10) => 2
choices(100) => 0
choices(111) => 1
choices(250) => 2
choices(360) => 0
If you are given three sticks, you may or may not be able to arrange them in a triangle.
If any of the three lengths is greater than the sum of the other two, then you cannot form a triangle. Otherwise, you can. If the sum of two lengths equals the third, they form what is called a "degenerate triangle."
Write a function is_triangle that consumes three positive integers (s1, s2, and s3) representing the lengths of three sticks and returns one of the following:
"No triangle exists" if no triangle can be built with the three sticks"Degenerate triangle exists" if only a degenerate triangle exists for sticks of these lengths"Triangle exists" if a triangle can be made from the sticks
Solution:
import check
def is_triangle(s1, s2, s3):
'''
returns "No triangle exists" if no non-degenerate triangle can be build
with sticks of these lengths,s1,s2,s3; "Degenerate triangle exists" if only
a degenerate triangle exists for sticks of these lengths,s1,s2,s3; "Triangle
exists" if a triangle can be made from sticks of these lengths,s1,s2,s3.
is_triangle: Nat Nat Nat -> Str
requires: s1,s2,s3 > 0
Examples:
is_triangle(2,3,4) => "Triangle exists"
is_triangle(2,3,5) => "Degenerate triangle exists"
is_triangle(2,3,8) => "No triangle exists"
'''
if s1 > s2+s3 or s2 > s1+s3 or s3 > s1+s2:
return "No triangle exists"
elif s1 == s2+s3 or s2 == s1+s3 or s3 == s1+s2:
return "Degenerate triangle exists"
else:
return "Triangle exists"
# Tests:
check.expect("tri-t1-1", is_triangle(2,3,4), "Triangle exists")
check.expect("tri-t1-2", is_triangle(4,3,2), "Triangle exists")
check.expect("tri-t1-3", is_triangle(3,4,2), "Triangle exists")
check.expect("tri-t2-1", is_triangle(2,3,5), "Degenerate triangle exists")
check.expect("tri-t2-2", is_triangle(3,5,2), "Degenerate triangle exists")
check.expect("tri-t2-3", is_triangle(5,3,2), "Degenerate triangle exists")
check.expect("tri-t3-1", is_triangle(2,3,8), "No triangle exists")
check.expect("tri-t3-2", is_triangle(3,8,2), "No triangle exists")
check.expect("tri-t3-3", is_triangle(8,2,3), "No triangle exists")
When we call return, the function automatically stops despite any further if statements. Thus, the following code is equivalent:
def alt_is_triangle(s1, s2, s3):
if s1 > s2+s3 or s2 > s1+s3 or s3 > s1+s2:
return "No triangle exists"
elif s1 == s2+s3 or s2 == s1+s3 or s3 == s1+s2:
return "Degenerate triangle exists"
return "Triangle exists"
Fermat's Last Theorem states that given positive integers a, b, and n, there exists no integer c for which a^n+b^n=c^n unless n=2. Although Fermat
wrote the statement of this theorem in the margin of a book in 1637, it was not proven until 1995 (and not for lack of trying - thousands of incorrect proofs
of the theorem were put forward before it was finally proven).
Write a function fermat_check that consumes four positive integers, a, b, c, and n.
- If n = 2, and a^2+b^2=c^2, then your function should return
"Pythagorean triple".
- If n = 2, and a^2+b^2 is not c^2, then your function should return
"Not a Pythagorean triple".
- If n > 2, and a^n+b^n=c^n, then your function should return
"Fermat was wrong!", as you have found a counterexample to Fermat’s Last Theorem.
- Otherwise, your function should return
"Not a counterexample".
Solution:
import check
def fermat_check(a, b, c, n):
'''
checks if (a,b,c) form a Pythagorean triple, and returns a string if n == 2.
If n > 2, checks if a^n + b^n = c^n (which would be a counterexample to
Fermat's Last Theorem), and returns an appropriate string.
fermat_check: Nat Nat Nat Nat -> Str
requires: a > 0, b > 0, c > 0, n > 1
Examples:
fermat_check(3, 4, 5, 2) => "Pythagorean triple"
fermat_check(3, 4, 6, 2) => "Not a Pythagorean triple"
fermat_check(3, 4, 5, 3) => "Not a counterexample"
Since no counterexample exists, we don't know anything
that will yield "Fermat was wrong".
'''
if n == 2:
if a*a + b*b == c*c:
return "Pythagorean triple"
else:
return "Not a Pythagorean triple"
else:
if a**n + b**n == c**n:
return "Fermat was wrong!"
else:
return "Not a counterexample"
# Tests:
check.expect("n=2 PT", fermat_check(3, 4, 5, 2), "Pythagorean triple")
check.expect("n=2 NAPT", fermat_check(3, 4, 6, 2), "Not a Pythagorean triple")
check.expect("n>2 NAC", fermat_check(3, 4, 5, 3), "Not a counterexample")
-
A perfect number is a positive integer that is equal to the sum of its proper positive divisors (i.e. the sum of its positive divisors excluding the number itself). Write a function is_perfect_num that consumes a positive integer n. The function returns True if n is a perfect number, False otherwise.
For example, is_perfect_num(6) => True (because 1+2+3 = 6).
Solution:
import check
def sum_divisors(n, divisor):
'''
returns the sum of the proper divisors of n starting from divisor.
sum_divisors: Nat Nat -> Nat
requires: n > 0
'''
if divisor < 1:
return 0
elif divisor == 1:
return 1
elif n % divisor == 0:
return divisor + sum_divisors(n, divisor - 1)
else:
return sum_divisors(n, divisor - 1)
def is_perfect_num(n):
'''
returns True if n is a perfect number, and False otherwise.
is_perfect_num: Nat -> Bool
requires: n > 0
Examples:
is_perfect_num(6) => True
is_perfect_num(1) => False
'''
sum_of_divisors = sum_divisors(n, n-1)
return sum_of_divisors == n
# Tests
check.expect("n=1 False", is_perfect_num(1), False)
check.expect("n=2 False", is_perfect_num(2), False)
check.expect("n=6 True", is_perfect_num(6), True)
check.expect("n=28 True", is_perfect_num(28), True)
check.expect("n=100 False", is_perfect_num(100), False)
|